package william.array;

/**
 * @author ZhangShenao
 * @date 2024/2/29
 * @description <a href="https://leetcode.cn/problems/remove-duplicates-from-sorted-array-ii/">...</a>
 */
public class Leetcode80_删除有序数组中的重复项2 {
    /**
     * 采用双指针法
     * 指针i用于遍历数组
     * 指针lastNonDup用于记录最后一个不重复的元素的位置,[0,lastNonDup)范围内的元素均不重复
     * 因为最多保留两个重复元素,因此lastNonDup初始=2
     * 从下标2开始遍历数组
     * 利用数组的有序性,如果当前元素与nums[lastNonDup-2]不相等,即与上上个被保留的元素不相等,则当前元素应该被保留,将当前元素赋值到lastNonDup位置,并将lastNonDup+1
     * 时间复杂度O(N)
     * 空间复杂度O(1)
     */
    public int removeDuplicates(int[] nums) {
        //边界条件校验
        if (nums == null || nums.length < 1) {
            return 0;
        }

        //采用双指针法
        //指针i用于遍历数组
        //指针lastNonDup用于记录最后一个不重复的元素的位置,[0,lastNonDup)范围内的元素均不重复
        int lastNonDup = 2;

        //从下标2开始遍历数组
        for (int i = 2; i < nums.length; i++) {
            //如果当前元素与nums[lastNonDup-2]不相等,即与上上个被保留的元素不相等,则当前元素应该被保留,将当前元素赋值到lastNonDup位置,并将lastNonDup+1
            if (nums[i] != nums[lastNonDup - 2]) {
                nums[lastNonDup++] = nums[i];
            }
        }

        //lastNonDup即为最终结果,直接返回
        return lastNonDup;

    }

}
